Rendering complex geometric models at interactive rates is a challenging problem in computer graphics. While rendering performance is continually improving, significant gains can be obtained by adapting the complexity of a geometric model to its contribution to a rendered graphical image. Within traditional modeling systems known in the computer graphics art, detailed geometric models are created by applying versatile modeling operations (e.g., extrusion, constructive solid geometry, and freeform deformations) to a vast array of geometric primitives used to define a graphical object or image. The geometric primitives typically include triangles, polygons, and other multi-sided shapes. For efficient display, the resulting geometric models are often transformed into polygonal approximations called "meshes."
Modeling systems for computer graphics and three-dimensional scanning systems commonly produce triangle meshes of high complexity. The geometry of a triangulated model used for a triangle mesh is typically denoted as a tuple (K, V) where the abstract simplicial complex K is a combinatorial structure specifying the adjacency of vertices, edges, faces, etc. in a geometric model, and V is a set of vertex positions specifying the shape of the model in R.sup.3 space.
High complexity triangle meshes are difficult to render, store and transmit within a computer graphics system. One approach to speed up rendering is to replace a complex triangular mesh by a set of level-of-detail (LOD) approximations. For rendering, level-of-detail approximations can be precomputed automatically using mesh simplification methods know in the art. For efficient storage and transmission, effective mesh compression schemes known in the art are used.
High complexity meshes are often stored as progressive meshes. In progressive mesh form, an arbitrary mesh M.sup.n is stored as a coarse bash mesh M.sup.0 together with a sequence of N-data structure records that indicate how to incrementally refine M.sup.0 into M.sup.n. The data structure records encodes information associated with elementary transformations on the mesh. In addition to defining a continuous sequence of approximations, M.sup.0, . . . , M.sup.n, the progressive mesh representation supports smooth visual transitions (e.g., geomorphs), allows progressive transmission of mesh data, and provides an effective mesh progressive scheme. For more information see, "Progressive Meshes," by Hugues Hoppe, ACM SIGGRAPH'96 Proceedings, pp. 99-108.
Using progressive mesh representations for geometric modeling in computer graphics has several drawbacks. One drawback with progressive mesh representations is that they can only represent triangulations used for triangular models that correspond to orientable two-dimensional manifolds. As is known in the art, a manifold is a topological space defined such that every point has a neighborhood which is homeomorphic (i.e., has a continuous one-to-one mapping) to the interior of a sphere in Euclidean space of the same number of dimensions. A neighborhood for a manifold is the set of all points whose distances from a given point fall within a pre-determined range.
Triangulated models that cannot be represented by progressive mesh representations include one-dimensional manifolds (e.g., open and closed curves), higher dimensional polyhedra (e.g., triangulated volumes), non-orientable surfaces (e.g., Mobius strips), non-manifolds (e.g., two cubes joined along an edge), and geometric models of mixed dimensionality. As is known in the art, a Mobius strip is a one-edged geometric surface with only one continuous side, formed by giving a 180.degree. twist to a narrow, rectangular strip and then connecting the two ends together.
Another problem associated with progressive mesh representations is that the expression of the progressive mesh transformations constrains all meshes in the progressive mesh sequence M.sup.0, . . . , M.sup.n to have the same topological type. Thus, when a progressive mesh representation is topologically complex, the simplified base mesh M .sup.0 in the progressive mesh representation may still have multiple geometric shapes instead of a single geometric shape. For example, if a triangular progressive mesh representation M is topologically complex, a simplified base mesh M.sup.0 in a progressive mesh representation may be reduced to multiple triangles instead of a single triangle which is the desired simplification.
A problem with triangulated models is that using simplification techniques known in the art, triangles can not be simplified into lower-dimensional representations when a coarser approximation of a model is created. This limits the type of coarser approximation that can be created. One simplification technique known in the art is to encode a sequence of geometric models using a sequence of vertex split transformations and allow the topological type of the models to change during the refinement. However, only triangles of the model are tracked, and arbitrary primitives cannot be encoded. Triangles that collapse are removed from the model. Thus, triangles cannot be collapsed into edges, and edges cannot be collapsed into vertices, thereby limiting the coarser model. See "Smooth Levels of Detail" by Dieter Schmalstieg and Gemot Schaufler, Proceedings of IEEE 1997 Virtual Reality Annual International Symposium, 1997, pp. 12-19 for more information.
In accordance with an illustrative embodiment of the current invention, the problems associated with using progressive mesh representations and triangulated models for complex geometric models in computer graphics are overcome. A method for creating a generalized representation of an arbitrary geometric model using a progressive simplicial complex that permits topological changes in the geometric model is presented. As is known in the art, a simplicial complex is a set of elements called "simplices" which are contained within a Euclidean space of a specified number of dimensions. The simplices have one more boundary point (e.g., d+1) than the specified number of dimensions (e.g., d) being used. A simplex of zero dimensions is a point, of one dimension is a line segment or edge, of two dimensions is a triangle and its interior, of three dimensions is a tetrahedron and its interior, etc. In an illustrative embodiment of the present invention, the progressive simplicial complex expresses an arbitrary geometric model (e.g., including a model of any dimension, non-orientable, non-manifold models and models of mixed dimensionality) as a single vertex and a set of transformation data determined as a result of successive refinements applied to an initial approximation. The single vertex and set of transformation data is useful for rendering the geometric model and transmitting the geometric model over a computer network like the Internet or an intranet for use in computer games and other applications.
In an illustrative embodiment of the present invention, an arbitrary geometric model M comprises a tuple (K, V, D, A) where tuple member K is a simplicial complex, tuple member V is a set of vertex positions that determine the geometric realization of K, tuple member D is a set of simplex attributes, and tuple member A is a set of areas for the principal simplices of K. However, more or fewer tuple members could be used in the geometric model (e.g., M=(K, V)).
The method for creating progressive simplicial complexes includes approximating an arbitrary geometric model M stored as a first approximation M.sup.i, where M.sup.i has i-vertices. The first approximation M.sup.i is transformed with a progressive simplicial complex transformation t.sup.i to create a second approximation M.sup.i-1 , where the second approximation M.sup.i-1 has i-1 vertices. The progressive simplicial complex transformation t.sup.i-1 transforms one or more of K.sup.i, V.sup.i, D.sup.i or A.sup.i to create M.sup.i-1 and will be explained in detail below. As each progressive simplicial complex transformation is completed, transformation data is recorded which allows the transformation to be inverted at a later time.
The progressive simplicial complex transformations are repeated on the approximations until a final approximation M.sup.f is created that has a predetermined number of vertices. In an illustrative embodiment of the present invention, the final approximation has one vertex M.sup.f =M.sup.1. However, other final approximations containing more than one vertex could also be used (e.g., M.sup.f =M.sup.2, M.sup.f =M.sup.3, etc.) The final approximation M.sup.1 and the set of saved transformation data corresponding to transformations {t.sup.i-1 , . . . , t.sup.1 } forms a progressive simplicial complex P. That is, the tuple (M.sup.1, {t.sup.1-1, . . . , t.sup.1 }) forms a progressive simplicial complex representation P of the geometric model M where M.sub.1 is the final approximation within one vertex and {t.sup.i-1, . . . , t.sup.1 } is the set of transformations.
The method for creating a progressive simplicial complex allows any arbitrary geometric model M (e.g., a model of any dimension, non-orientable, non-manifold, mixed dimensional, etc.) to be expressed as a progressive simplicial complex. Successive refinements with transformations on the progressive simplicial complex result in a principal simplex with a single vertex. A principal simplex has no parent in the progressive simplicial complex. A parent is a top most entity in a hierarchical scheme. The successive refinement encodes changes to both the geometry and topology of the arbitrary model M. Thus, both geometric and topological complexity can be recovered progressively using the progressive simplicial complex and the geometric model is not constrained to one topology type. The progressive simplicial complex can be used for progressive transmission of an approximated geometric model over a computer network such as the Internet or an intranet for a real-time computer game or other application. It also allows easier rendering of an arbitrary geometric model M.
The foregoing and other features and advantages of an illustrative embodiment of the present invention will be more readily apparent from the following detailed description, which proceeds with reference to the accompanying drawings.